package com.ryujung.sort;

import java.util.Arrays;

public class InsertionSort {

    /**
     * 插入排序（Insertion-Sort）的算法描述是一种简单直观
     * 的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，
     * 在已排序序列中从后向前扫描，找到相应位置并插入。
     */
    public static void insertionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int cur = arr[i + 1];
            // 在有序序列中找到 cur 的位置
            int j = i;
            while(j>=0 && arr[j] > cur) {
                arr[j + 1] = arr[j];
                j--; 
            }
            arr[j + 1] = cur;
        }
    }

    public static void main(String[] args) {
        int[] arr1 = { 5, 3, 8, 6, 4 };
        int[] arr2 = { 3, 1, 4, 2, 5 };
        int[] arr3 = { 9, 7, 6, 2, 4, 3, 1, 5, 8 };
        insertionSort(arr1);
        System.out.println(Arrays.toString(arr1));
        insertionSort(arr2);
        System.out.println(Arrays.toString(arr2));
        insertionSort(arr3);
        System.out.println(Arrays.toString(arr3));
    }

}